#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
Implementation of Beta, Copyright (c) 2007-2008 Vesa Linja-aho
Licensed under the LGPL license:
http://www.gnu.org/licenses/lgpl.html

The implementation is based on a Finnish textbook:
  Karsson, Koskenniemi: "Beta-ohjelma kielentutkijan apuvälineenä", 1990
  (later: "the book" or "textbook")
Version: 0.42 20.4.2008 (bugs fixed)

ToDo (highest priority first):

- Use unicode strings everywhere
- Some error handling (= user-friendly error messages)

Bugs:

- No known bugs at present

Changes from previous version 0.41:

- The pointer begins now from between the first two #:s, not before them
- The "move" parameter values 1 and 6 now behave correctly
- '#' Now acts correctly as a LIMITOR
- Now empty input line in file does NOT terminate beta
- Execute "print" -statement only if there is something to print (avoids unwanted newlines)

Functions used in the code:
- explode(string) - converts string into a list of characters
- applyrules(state,outbuf,inbuf,destination,indices=0) - applies the rule set to a string
- readrules() - read rules from a file

- newbranch - create a new branch for rule tree
- findrule - find matching rules for x-part from rule tree
- addtotree - add a rule to the rule tree
- maketree - construct the tree from the rules read

'''

import sys # for command line arguments and stdin processing

# GLOBAL DEFINITIONS

DEBUG=0 # 1 for debugging
MODE=1 # 1 = ask only one 0 = ask many
TRACE=False # 0 = trace off 1 = trace on - can be toggled by inputting ##

# GLOBAL VARIABLES
charsets = {}
statesets = {}
rules = []

# FUNCTIONS

# Functions for rule tree

def newbranch(x, idx):
   # Creates a new branch
   temp = {x[-1]:{'RULES':[idx]}} # create the rightmost node
   x = x[:-1] # remove last char
   while len(x)!=0:
        temp = {x[-1]:temp}
        x = x[:-1]
   return temp

def findrule(tree,x,bestrule): # Give empty [] as argument
    # Traverses the tree to find if there is match for x
    if tree.has_key('RULES'): # Save the match
       temp = list(tree['RULES']) # Copy the object, avoid messing the tree
       temp.reverse()
       bestrule.extend(temp)
    if len(x)>0 and tree.has_key(x[0]):
        return findrule(tree[x[0]],x[1:],bestrule)
    else:
        return bestrule
        
def addtotree(tree, x, idx):
    # First traverse the tree as long as you can
    # Then create a new branch from remaining chars and join it
    if len(x)>0 and tree.has_key(x[0]):
        return addtotree(tree[x[0]],x[1:],idx)
    else:
        if len(x)>1:
            tree[x[0]]=newbranch(x[1:], idx)
        if len(x)==1:
            tree[x]={'RULES':[idx]}
        if len(x)==0:
            if tree.has_key('RULES'):
               tree['RULES'].append(idx)
            else:
               tree['RULES']=[idx]

def maketree(rules):
   i = 0
   retval = {}
   while i < len(rules):
      addtotree(retval,rules[i][0],i)
      i = i + 1 
   return retval
   
# End of functions for rule tree

# Apply ruleset and print results to destination (stdout or file)
def applyrules(state,outbuf,inbuf,destination,indices=0): 

    # Traverse the rule tree to find match by x part
    while len(inbuf)!=0:
        if indices == 0:
           indices = findrule(ruletree,inbuf,[]) # Indices for applicable by x part
           indices.reverse() # The longest rules first
        
        if DEBUG==1: print "Only these rules passed the X check: ", indices

        # Find rule(s) matching the input
        bestrule = -1 # The index of best (longest) rule is saved in this var

        # If X match is found, test matches for state, lc, 
        if not (indices==[]):
           for j in indices:
               # First check for state match
               #    0 = ignore                is state in the stateset
               if ((rules[j][2][2] == '0') or str(state) in statesets[rules[j][2][2]]):
                   # lc-test: 0 = ignore      complement                                                                              for first element  last element of outbuf is in lc-rule
                   if(rules[j][2][0]=='0' or (rules[j][2][0][0]=="-" and not(outbuf[-1] in charsets[rules[j][2][0]].lstrip("-"))) or (len(outbuf)!=0 and (outbuf[-1] in charsets[rules[j][2][0]]))):
                       # and if rc-rules is zero or inbuf is shorter/eq the rule or last input char equals rc
                       if not(rules[j][2][1]!='0' and (len(inbuf)==len(rules[j][0]))): # reject if rc not omitted and rc is "out of bounds"
                           #  rc-check:               complement check                                                                         # normal check, like lc check
                           if rules[j][2][1]=='0' or (rules[j][2][1][0]=="-" and not (inbuf[len(rules[j][0])]) in charsets[rules[j][2][1].lstrip("-")] ) or (rules[j][2][1][0]!="-" and inbuf[len(rules[j][0])] in charsets[rules[j][2][1]]):
                             if bestrule ==-1 or len(rules[j][0])>len(rules[bestrule][0]):
                               bestrule=j # Apply only if this rule is longer rule
                               if DEBUG==1:
                                   print "Rule: ",rules[j], " (index " , j, ")matches."
        # Apply the rule, if rule is  found (bestrule !=1)
        if bestrule==-1:
            outbuf.append(inbuf[0]) # No rule found --> do nothing
            inbuf = inbuf[1:] # Remove the first character from inbuf
        else: # apply the rule
            if TRACE:
                print "%s; %s; " % (rules[bestrule][0],rules[bestrule][1]),
                for i in rules[bestrule][2]:
                    print i, # print without newline
                print ''
            # The undeterministic applying of the rule
            if rules[bestrule][2][5] in ('2','3'): # '3' only for backwards compatibility
                queue = list(outbuf) # Save a copy of the buffer
                if TRACE: print "Pushed to the Stack"
                applyrules(state,outbuf,inbuf,destination,indices[indices.index(bestrule)+1:]) # Start a new branch
                if TRACE: print "From the Stack:",
                outbuf=list(queue) # Restore the copy of the buffer
            
            outbuf = outbuf + explode(rules[bestrule][1]) # Finally, execute the substitution
            inbuf = inbuf[len(rules[bestrule][0]):] # Remove the characters substituted from inbuf
            # Handle the pointer movement
            move=int(rules[bestrule][2][4])
            if move==1: # Move pointer to beginning after the ##-signs
                inbuf = outbuf + inbuf
                inbuf = inbuf[2:]
                outbuf = ["#","#"]
            if move==2: # Pointer to lc - move (len(y) + 1 ) from outbuf to inbuf
                tmp = outbuf[-(len(rules[bestrule][1])+1):]
                inbuf = tmp + inbuf
                outbuf = outbuf[:-(len(rules[bestrule][1])+1)]
            if move==3: # Pointer to beginning of y - move (len(y) ) from outbuf to inbuf
                tmp = outbuf[-(len(rules[bestrule][1])):]
                inbuf = tmp + inbuf
                outbuf = outbuf[:-(len(rules[bestrule][1]))]
            if move==4: # Pointer to last character of y - move one char from out to in
                tmp = outbuf[-1:]
                inbuf = tmp + inbuf
                outbuf = outbuf[:-1]
            if move==6: # Pointer to the end
                outbuf = outbuf + inbuf
                outbuf = outbuf[:-2]
                inbuf = ["#","#"]
            if move==0: # Reject the whole data
                outbuf = []
                inbuf = []
            if move==7: # Accept and print immediately
                outbuf = outbuf + inbuf
                inbuf = []

            if int(rules[bestrule][2][3]) > 0: # Change state
                state = int(rules[bestrule][2][3])
            if int(rules[bestrule][2][3]) < 0:
                state = state - int(rules[bestrule][2][3])

            if TRACE:
                print '    ',''.join(outbuf),">>>",''.join(inbuf), "-->",state

        if DEBUG==1:
            print "Inbuffer: ",inbuf
            print "Outbuffer: ",outbuf
            print "State: ", state
            raw_input("")
        indices = 0
    outbuf = ''.join(outbuf)
    outbuf = outbuf[2:-2] # Strip the ## from end and beginning
    if len(outbuf)!=0: # Print only if there is something to print (avoids unwanted newlines)
       if destination=='stdout':
          print outbuf
       else:
          print >>destination, outbuf
       
# FUNCTION Convert string to list of characters
def explode(x):
    retval = []
    for i in x:
        retval.append(i)
    return retval
    

def readrules(filename):
    # Open the rule file
    rulefile = open(filename, "r")

    parsermemory=[]

    for line in rulefile:
        # Detect the rows delimiting charset, stateset and rule sets
        if line.startswith("CHARACTER-SETS"):
            mode = 1 # Now reading charsets
            continue
        if line.startswith("STATE-SETS"):
            mode = 2 # Now reading statesets
            continue
        if line.startswith("RULES"):
            mode = 3 # Now reading rules
            continue

        # Skip empty lines
        if line == "\n":
            continue 

        # Bypass the comment lines
        if line.startswith("!"):
            continue
        
        if mode == 1:
            temp = []
            line = line.replace("%!","!") # Deal with escaped !
            for i in line[line.find(":")+1:].strip().split():
               # Deal with escaped chars and BLANK
               i = i.replace('%%','_ESCAPED_PERC_SIGN')
               i = i.replace('BLANK',' ')
               i = i.replace('%n','\n')
               i = i.replace('%t','\t')
               i = i.replace('_ESCAPED_PERC_SIGN','%')
               temp.append(i)
            charsets[line[:line.find(":")].strip()] = tuple(temp)

        if mode == 2:
            statesets[line.split(":")[0].strip()] = tuple(line.split(":")[1].strip().split())

        if mode == 3:
           #print "Reading:", line
           temp = line.replace('%%','_ESCAPED_PERC_SIGN') # Deal with escaped %
           temp = temp.replace("%;","_ESCAPED_SEMICOLON_CHARACTER") # Deal with escaped ;  ...
           temp = temp.replace("%!","!") # Deal with escaped ! in the beginning of the line
           temp = temp.split(";") # Split the string by ; -delimiters
           # ... and deal also with other escaped chars:
           
           temp[0] = temp[0].replace("_ESCAPED_SEMICOLON_CHARACTER",";")
           temp[0] = temp[0].replace('%n','\n')
           temp[0] = temp[0].replace('%t','\t')
           temp[0] = temp[0].replace('_ESCAPED_PERC_SIGN','%')
           temp[1] = temp[1].replace("_ESCAPED_SEMICOLON_CHARACTER",";")
           temp[1] = temp[1].replace('%n','\n')
           temp[1] = temp[1].replace('%t','\t')
           temp[1] = temp[1].replace('_ESCAPED_PERC_SIGN','%')
           
           temp[1] = temp[1][1:] # Remove the first (space) character from Y
           
           #Strip the scrap after a "(" comment in rule file
           temp[2] = temp[2].split("(")[0]
            
           # "Remember" the conditions from previous row
           conditions = temp[2].split()

            # If parameters from the end of line are omitted, fetch them from memory
           while len(conditions)<6:
               conditions.append(parsermemory[len(conditions)])
           parsermemory=conditions

           temp = (temp[0],temp[1],tuple(conditions))
           rules.append(temp)
    rulefile.close()

    # End of parser function

# The "main program"

# If no parameters specified, give instructions
if len(sys.argv)==1:
   print "Usage:", sys.argv[0], "rulefile [inputfile] [outputfile]"
   print "For example: sys.argv[0]", "rules.bta corpus.txt"
   sys.exit(0)
   #RULE_FILE="wgen.bta"

if len(sys.argv)>1: # The rule file
   RULE_FILE=sys.argv[1]

readrules(RULE_FILE) # Read the rules from file
ruletree = maketree(rules) # Make the tree from rule set

inputfile=None
if len(sys.argv)>2: # The input data file
   inputfile = open(sys.argv[2], "r")
   inputdata = inputfile.read()
   if not charsets.has_key("LIMITOR"):
      inputdata = inputdata.split() # If no LIMITOR, just split()
   else:
      import re
      limitors = '[' + ''.join(list(charsets["LIMITOR"]))
      if "#" in charsets["LIMITOR"]: limitors += "\n" # '#' as limitor means '\n' (page 36 in the book)
      limitors=limitors + ']'
      #print "x",limitors,"x"
      inputdata = re.split(limitors,inputdata) # NOTE: Consecutive limitors are NOT considered as one!
      #print inputdata
   

destination = "stdout"

if len(sys.argv)>3: # The output file
   destination = open(sys.argv[3], "w")
   
#data = "-"
while 1:
    inbufi = ["#"]

    if inputfile==None:
       data = sys.stdin.readline().strip() #WAS: data = raw_input("BETA>") --> piping didn't work
       if data == '': break
    else:
       if len(inputdata)!=0: data = inputdata.pop(0)
       else: break # Break when whole file read
    # Trace on/off
    if data=='##':
        TRACE = not TRACE
        if TRACE:
            print "Trace Now ON"
        else: print "Trace Now OFF"
        continue
    
    # Convert the input string into a list
    for char in data:
        inbufi.append(char)
    inbufi = inbufi + ["#","#"]

    applyrules(1,["#"],inbufi,destination)


# Close open files

if len(sys.argv)>3: # Close the output file
   destination.close()

if inputfile!=None: # Close the input file
    inputfile.close()
